package com.example.demo.leetcode.codetop;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author xujimou
 * @version 2.0
 * @Description
 *
 * 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：nums = [1,2,3]
 * 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
 * 示例 2：
 *
 * 输入：nums = [0,1]
 * 输出：[[0,1],[1,0]]
 * 示例 3：
 *
 * 输入：nums = [1]
 * 输出：[[1]]
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/permutations
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @date 2022/3/15 11:06
 */
public class 全排列 {

    List<List<Integer>>  res = new ArrayList<>();

    public List<List<Integer>> permute(int[] nums) {

        // flag 数组 表示下标对应的哪个 数字是否可以使用，刚开始全部可以使用
        boolean [] flag = new boolean [nums.length];
        Arrays.fill(flag,true);
        process(new ArrayList<>(), flag, nums,0);
        return res;
    }

    public void process(List<Integer> list, boolean [] flag, int [] nums, int ceng){

        // ceng 表示递归到第几层
        if(ceng > nums.length){
            return;
        }
        if(ceng == nums.length){
            res.add(new ArrayList<>(list));
            return;
        }

        for(int i=0;i<nums.length;i++){
            if(flag[i]){
                list.add(nums[i]);
                flag[i] = false;
                process(list,flag,nums,ceng+1);
                //为啥删最后一个？ 假如第一层 数字是1， 递归下来，1-2-3，删除从3开始删
                list.remove(list.size()-1);
                flag[i] = true;
            }

        }

    }


}
